package com.springboot.test.sort;

import java.util.Arrays;

/**
 *  基数排序
 */
public class RadixSort {

    public static void main(String[] args) throws Exception {

        int[] arr = {2,35,65,123,6,7,12,1};

        System.out.println(Arrays.toString(arr));

        sort(arr);

        System.out.println(Arrays.toString(arr));
    }

//    public static void sort(int[] arr){
//
//        // 找出最大位数
//        int maxDigit = getMaxLength(arr);
//
//        int divisor = 10;
//        int mod = 1;
//        for (int i = 0; i < maxDigit; i++, divisor *= 10, mod *= 10) {
//            // 创建并初始化桶  暂时不考虑负数  桶大小10的情况下 每位桶的个数应该是10个
//            int[][] buckets = new int[10][0];
//            // 将待排序元素分配到桶
//            for (int j = 0; j < arr.length; j++) {
//                // 取当前位的元素
//                int bucket = (arr[i] / divisor) % mod;
//                buckets[bucket] = arrAppend(buckets[bucket], arr[j]);
//            }
//        }
//        // 桶排序
//        // 合并数据
//
//    }

    public static int getMaxLength(int[] arr){
        int maxLength = 0;
        for (int i = 0; i < arr.length; i++) {
            int length = 1;
            int tmp = arr[i];
            while ((tmp = tmp / 10) != 0){
                length ++;
            }
            if(length > maxLength){
                maxLength = length;
            }
        }
        return maxLength;
    }

    public static int[] sort(int[] sourceArray) throws Exception {

        int maxDigit = getMaxDigit(sourceArray);
        return radixSort(sourceArray, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private static int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected static int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private static int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}
